package com.base.ch01;

/**
 * Created by xingyuchao@zto.cn on 2017-12-07.
 * 自定义有序数组实现
 * 包含自删改查操作
 */
public class MyOrderArray {

    private long[] arr;

    /**表示有效数据的长度*/
    private int elements;

    /**
     * 初始化一个50个长度的long型数组
     */
    public MyOrderArray(){
        arr = new long[50];
    }

    /**
     * 初始化一个固定大小的数组
     * @param maxSize
     */
    public MyOrderArray(int maxSize){
        arr = new long[maxSize];
    }

    /**
     * 新增元素,有序数组新增需要从后往前复制，之后插入
     * @param value
     */
    public void insert(long value){
        int i;
        for (i = 0; i < elements ; i++){
            if(arr[i] > value){
                break;
            }
        }
        for (int j = elements; j > i; j--){
            arr[j] = arr[j-1];
        }
        arr[i] = value;
        elements++;
    }

    /**
     * 显示所有数据
     */
    public void display() {
        System.out.print("[");
        for(int i = 0 ; i < elements ;i++){
            System.out.print(arr[i] + " ");
        }
        System.out.println("]");
    }

    /**
     * 查询数据
     * @param value
     * @return
     */
    public int search(long value) {
        int i;
        for (i = 0 ; i < elements; i++) {
            if(arr[i] == value){
                break;
            }
        }
        //如果没有获取到返回-1,
        if(i == elements){
            return -1;
        }else{
            return i;
        }
    }

    /**
     * 二分法查找数据
     */
    public int binarySearch(long value) {
        int middle = 0;
        int low = 0;
        int pow = elements;

        while(true) {
            middle = (pow + low) / 2;
            if(arr[middle] == value) {
                return middle;
            } else if(low > pow) {
                return -1;
            } else {
                if(arr[middle] > value) {
                    pow = middle - 1;
                } else {
                    low = middle + 1;
                }
            }
        }
    }

    /**
     * 根据索引查询数组元素
     * @param index
     * @return
     */
    public long get(int index) {
        if(index >= elements || index < 0){
            throw new ArrayIndexOutOfBoundsException();
        }else{
            return arr[index];
        }
    }

    /**
     * 根据索引删除数组
     * @param index
     */
    public void delete(int index) {
        if(index >= elements || index < 0){
            throw new ArrayIndexOutOfBoundsException();
        }else{
            //将后一个元素赋值给前一个元素，并且有效长度要-1
            for (int i = index; index < elements ; i++){
                arr[index] = arr[index + 1];
                index ++;
            }
            elements -- ;
        }

    }

    /**
     * 根据索引更新元素
     * @param index
     * @param newvalue
     */
    public void change(int index, int newvalue) {
        if(index >= elements || index < 0){
            throw new ArrayIndexOutOfBoundsException();
        }else{
            arr[index] = newvalue;
        }
    }

    /**
     * 返回数组的长度
     * @return
     */
    public int size(){
        return elements;
    }
}